package org.example.myleet.p474;

/**
 * 三维动态规划
 */
public class Solution {

    public int findMaxForm(String[] strs, int m, int n) {
        //dp[i][j][k]表示在第i个字符（i从1开始）时，使用了j个0、k个1的情况下能得到的最大子集长度
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        for (int i = 0; i < strs.length; ++i) {
            int zero = 0, one = 0;
            for (int x = 0; x < strs[i].length(); ++x) {
                char c = strs[i].charAt(x);
                if (c == '0') {
                    ++zero;
                } else if (c == '1') {
                    ++one;
                }
            }
            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k <= n; ++k) {
                    dp[i + 1][j][k] = dp[i][j][k];
                    if (j >= zero && k >= one) {
                        dp[i + 1][j][k] = Math.max(dp[i][j][k], dp[i][j - zero][k - one] + 1);
                    }
                }
            }
        }
        return dp[strs.length][m][n];
    }
}
